package server;

import java.util.ArrayList;

/**
 * Created by Zhao on 2017/10/22.
 */
public class DistanceCompute {


    private int deleteCost = 1;
    private int insertCost = 1;
    private int substituteCost = 1;



    private ArrayList<ArrayList<Integer>> distancesArray;
    private ArrayList<ArrayList<Integer> > insertionsArray;
    private ArrayList<ArrayList<Integer> > deletionsArray;

    private ArrayList<ArrayList<Integer>> belowDistanceArray;



    private boolean computeDistance(int[] content, int strCp ,int strPos) {
        int i = strPos;

        if(belowDistanceArray.size()<=i+1) belowDistanceArray.add(new ArrayList<Integer>());
        else belowDistanceArray.set(i+1,new ArrayList<Integer>());

        if(distancesArray.get(0).size()<=i+1) {
            for (int j=0; j<content.length+1;j++){
                distancesArray.get(j).add(new Integer(i+1));
                insertionsArray.get(j).add(new Integer(0));
                deletionsArray.get(j).add(new Integer(0));
            }
        }
        else {
            for (int j=0; j<content.length+1;j++){
                distancesArray.get(j).set(i + 1, i + 1);
                insertionsArray.get(j).set(i + 1, 0);
                deletionsArray.get(j).set(i+1,0);
            }
        }
        insertionsArray.get(0).set(i+1, i+1);

        for (int n=0; n<belowDistanceArray.get(i).size();n++) {
            int j = belowDistanceArray.get(i).get(n);
            if (strCp == content[j]) {
                distancesArray.get(j+1).set(i+1,distancesArray.get(j).get(i));
                deletionsArray.get(j+1).set(i+1,deletionsArray.get(j).get(i));
                insertionsArray.get(j+1).set(i+1,insertionsArray.get(j).get(i));
            }
            else {
                int delete = distancesArray.get(j+1).get(i) + deleteCost;
                int insert = distancesArray.get(j).get(i+1) + insertCost;
                int substitute = distancesArray.get(j).get(i) + substituteCost;

                if (insert<=delete && insert<=substitute) {
                    distancesArray.get(j+1).set(i+1,insert);
                    deletionsArray.get(j+1).set(i+1,deletionsArray.get(j).get(i+1));
                    insertionsArray.get(j+1).set(i+1,insertionsArray.get(j).get(i+1)+1);
                }
                else if (delete<=substitute){
                    distancesArray.get(j+1).set(i+1,delete);
                    deletionsArray.get(j+1).set(i+1,deletionsArray.get(j+1).get(i)+1);
                    insertionsArray.get(j+1).set(i+1,insertionsArray.get(j+1).get(i));
                }
                else {
                    distancesArray.get(j+1).set(i+1,substitute);
                    deletionsArray.get(j+1).set(i+1,deletionsArray.get(j).get(i));
                    insertionsArray.get(j+1).set(i+1,insertionsArray.get(j).get(i));
                }
            }

            if(j<content.length-1)
                belowDistanceArray.get(i+1).add(j+1);
        }
        return belowDistanceArray.get(i+1).size()>0;
    }



    public int annotate(String text,String query) {

        int[] content = codePoints1(text+" ");

        int[] compare = codePoints1(query);
		
		int ndistance = compare.length;

        double [] distancesPrevCol  = new double [compare.length+1];
        int [] insertionsPrevCol  = new int [compare.length+1];
        int [] deletionsPrevCol  = new int [compare.length+1];
        double [] distancesCol  = new double [compare.length+1];
        int [] insertionsCol  = new int [compare.length+1];
        int [] deletionsCol  = new int [compare.length+1];




        for (int i=0;i<compare.length+1;i++){
            distancesPrevCol[i] = i;
            deletionsPrevCol[i] = i;
        }

        double prevPrevDistance = Double.MAX_VALUE; // stores the distance 2 columns before. this is important to find the minimum distance
        for (int j=0; j<content.length;j++) {
            // distancesCol[0] = 0; //Unnecessary because Java initialize arrays with 0 automatically.
            for (int i=1;i<distancesCol.length;i++) {
                if (compare[i - 1] == content[j]) {
                    distancesCol[i] = distancesPrevCol[i - 1];
                    deletionsCol[i] = deletionsPrevCol[i - 1];
                    insertionsCol[i] = insertionsPrevCol[i - 1];
                }
                else {
                    double delete = distancesCol[i-1] + deleteCost;
                    double insert = distancesPrevCol[i] + insertCost;
                    double substitute = distancesPrevCol[i-1] + substituteCost;
                    if (delete<=insert && delete<=substitute) {
                        distancesCol[i] = delete;
                        deletionsCol[i] = deletionsCol[i-1] + 1;
                        insertionsCol[i] = insertionsCol[i-1];
                    }
                    else if (insert<=substitute){
                        distancesCol[i] = insert;
                        deletionsCol[i] = deletionsPrevCol[i];
                        insertionsCol[i] = insertionsPrevCol[i]+1;
                    }
                    else {
                        distancesCol[i] = substitute;
                        deletionsCol[i] = deletionsPrevCol[i-1];
                        insertionsCol[i] = insertionsPrevCol[i-1];
                    }
                }
            }
            double distance = distancesCol[compare.length];
            double prevDistance = distancesPrevCol[compare.length];

            if (true) {
                if (distance >= prevDistance && prevDistance <= prevPrevDistance) { // a minimum was found
                    if (true) {
                        int matchedRegionEnd = j;
                        int matchedRegionStart = (j) -(compare.length+insertionsPrevCol[compare.length]-deletionsPrevCol[compare.length]);
						
						if(prevDistance<ndistance)
                            ndistance = (int)prevDistance;

                        //System.out.println(Integer.toString(matchedRegionStart)+" "+Integer.toString(matchedRegionEnd));
                        //System.out.println(Double.toString(prevDistance));

                    }
                }
            }

            prevPrevDistance = distancesPrevCol[compare.length];
            for (int i=1; i<compare.length+1; i++) {
                distancesPrevCol[i] = distancesCol[i];
                insertionsPrevCol[i] = insertionsCol[i];
                deletionsPrevCol[i] = deletionsCol[i];

            }


        }
		
		return ndistance;



    }

    private static int[] codePoints1(String input) {
        int length = Character.codePointCount(input, 0, input.length());
        int word[] = new int[length];
        for (int i = 0, j = 0, cp = 0; i < input.length(); i += Character.charCount(cp)) {
            word[j++] = cp = input.codePointAt(i);
        }
        return word;
    }


    public static void main(String args[]) {

        DistanceCompute dc = new DistanceCompute();


        dc.annotate("bcgfgtggtddgdabcc","abc");

    }








}
